On the computational complexity of curing non-stoquastic Hamiltonians.

Quantum many-body systems whose Hamiltonians are non-stoquastic, i.e., have positive off-diagonal matrix elements in a given basis, are known to pose severe limitations on the efficiency of Quantum Monte Carlo algorithms designed to simulate them, due to the infamous sign problem. We study the computational complexity associated with 'curing' non-stoquastic Hamiltonians, i.e., transforming them into sign-problem-free ones. We prove that if such transformations are limited to single-qubit Clifford group elements or general single-qubit orthogonal matrices, finding the curing transformation is NP-complete. We discuss the implications of this result.

Resolution of the sign problem for a frustrated triplet of spins.

We propose a mechanism for solving the "negative sign problem"-the inability to assign non-negative weights to quantum Monte Carlo configurations-for a toy model consisting of a frustrated triplet of spin-1/2 particles interacting antiferromagnetically. The introduced technique is based on the systematic grouping of the weights of the recently developed off-diagonal series expansion of the canonical partition function [Phys. Rev. E 96, 063309 (2017)PREHBM2470-004510.1103/PhysRevE.96.063309]. We show that, although the examined model is easily diagonalizable, the sign problem it encounters can nonetheless be very pronounced, and we offer a systematic mechanism to resolve it. We discuss the prospects of generalizing the suggested scheme and the steps required to extend it to more general and larger spin models.

Temperature Scaling Law for Quantum Annealing Optimizers.

Physical implementations of quantum annealing unavoidably operate at finite temperatures. We point to a fundamental limitation of fixed finite temperature quantum annealers that prevents them from functioning as competitive scalable optimizers and show that to serve as optimizers annealer temperatures must be appropriately scaled down with problem size. We derive a temperature scaling law dictating that temperature must drop at the very least in a logarithmic manner but also possibly as a power law with problem size. We corroborate our results by experiment and simulations and discuss the implications of these to practical annealers.

Solving spin glasses with optimized trees of clustered spins.

We present an algorithm for the optimization and thermal equilibration of spin glasses, or more generally, cost functions of the Ising form H=∑_{〈ij〉}J_{ij}s_{i}s_{j}+∑_{i}h_{i}s_{i}, defined on graphs with arbitrary connectivity. The algorithm consists of two repeated steps: (i) the optimized construction of a random tree of spin clusters on the input problem graph, and (ii) the thermal sampling of the generated tree. The randomly generated trees are constructed so as to optimize a balance between the size of the tree and the complexity required to draw Boltzmann samples from it. We benchmark the algorithm on several classes of problems and demonstrate its advantages over existing approaches.

Advantages of Unfair Quantum Ground-State Sampling.

The debate around the potential superiority of quantum annealers over their classical counterparts has been ongoing since the inception of the field. Recent technological breakthroughs, which have led to the manufacture of experimental prototypes of quantum annealing optimizers with sizes approaching the practical regime, have reignited this discussion. However, the demonstration of quantum annealing speedups remains to this day an elusive albeit coveted goal. We examine the power of quantum annealers to provide a different type of quantum enhancement of practical relevance, namely, their ability to serve as useful samplers from the ground-state manifolds of combinatorial optimization problems. We study, both numerically by simulating stoquastic and non-stoquastic quantum annealing processes, and experimentally, using a prototypical quantum annealing processor, the ability of quantum annealers to sample the ground-states of spin glasses differently than thermal samplers. We demonstrate that (i) quantum annealers sample the ground-state manifolds of spin glasses very differently than thermal optimizers (ii) the nature of the quantum fluctuations driving the annealing process has a decisive effect on the final distribution, and (iii) the experimental quantum annealer samples ground-state manifolds significantly differently than thermal and ideal quantum annealers. We illustrate how quantum annealers may serve as powerful tools when complementing standard sampling algorithms.

Off-diagonal expansion quantum Monte Carlo.

We propose a Monte Carlo algorithm designed to simulate quantum as well as classical systems at equilibrium, bridging the algorithmic gap between quantum and classical thermal simulation algorithms. The method is based on a decomposition of the quantum partition function that can be viewed as a series expansion about its classical part. We argue that the algorithm not only provides a theoretical advancement in the field of quantum Monte Carlo simulations, but is optimally suited to tackle quantum many-body systems that exhibit a range of behaviors from "fully quantum" to "fully classical," in contrast to many existing methods. We demonstrate the advantages, sometimes by orders of magnitude, of the technique by comparing it against existing state-of-the-art schemes such as path integral quantum Monte Carlo and stochastic series expansion. We also illustrate how our method allows for the unification of quantum and classical thermal parallel tempering techniques into a single algorithm and discuss its practical significance.

Unraveling Quantum Annealers using Classical Hardness.

Recent advances in quantum technology have led to the development and manufacturing of experimental programmable quantum annealing optimizers that contain hundreds of quantum bits. These optimizers, commonly referred to as 'D-Wave' chips, promise to solve practical optimization problems potentially faster than conventional 'classical' computers. Attempts to quantify the quantum nature of these chips have been met with both excitement and skepticism but have also brought up numerous fundamental questions pertaining to the distinguishability of experimental quantum annealers from their classical thermal counterparts. Inspired by recent results in spin-glass theory that recognize 'temperature chaos' as the underlying mechanism responsible for the computational intractability of hard optimization problems, we devise a general method to quantify the performance of quantum annealers on optimization problems suffering from varying degrees of temperature chaos: A superior performance of quantum annealers over classical algorithms on these may allude to the role that quantum effects play in providing speedup. We utilize our method to experimentally study the D-Wave Two chip on different temperature-chaotic problems and find, surprisingly, that its performance scales unfavorably as compared to several analogous classical algorithms. We detect, quantify and discuss several purely classical effects that possibly mask the quantum behavior of the chip.

Excitation gap from optimized correlation functions in quantum Monte Carlo simulations.

We give a prescription for finding optimized correlation functions for the extraction of the gap to the first excited state within quantum Monte Carlo simulations. We demonstrate that optimized correlation functions provide a more accurate reading of the gap when compared to other "nonoptimized" correlation functions and are generally characterized by considerably larger signal-to-noise ratios. We also analyze the cost of the procedure and show that it is not computationally demanding. We illustrate the effectiveness of the proposed procedure by analyzing several exemplary many-body systems of interacting spin-1/2 particles.

Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems.

We determine the complexity of several constraint satisfaction problems using the quantum adiabatic algorithm in its simplest implementation. We do so by studying the size dependence of the gap to the first excited state of "typical" instances. We find that, at large sizes N, the complexity increases exponentially for all models that we study. We also compare our results against the complexity of the analogous classical algorithm WalkSAT and show that the harder the problem is for the classical algorithm, the harder it is also for the quantum adiabatic algorithm.

Strongly interacting atom lasers in three-dimensional optical lattices.

We show that the dynamical melting of a Mott insulator in a three-dimensional lattice leads to condensation at nonzero momenta, a phenomenon that can be used to generate strongly interacting atom lasers in optical lattices. For infinite on-site repulsion, the case considered here, the momenta at which bosons condense are determined analytically and found to have a simple dependence on the hopping amplitudes. The occupation of the condensates is shown to scale linearly with the total number of atoms in the initial Mott insulator. Our results are obtained by using a Gutzwiller-type mean-field approach, gauged against exact-diagonalization solutions of small systems.

Baby Skyrmions on the two-sphere.

We find the static multisoliton solutions of the baby Skyrme model on the two-sphere for topological charges 1< or =B< or =14. Numerical full-field results show that the charge-one Skyrmion is spherical, the charge-two Skyrmion is toroidal, and Skyrmions with higher charge all have point symmetries which are subgroups of O(3). We find that a rational map ansatz yields very good approximations to the full-field solutions. We point out a strong connection between the discrete symmetries of our solutions and those of corresponding solutions of the three-dimensional Skyrme model.

No-broadcasting theorem and its classical counterpart.

Although it is widely accepted that "no-broadcasting"-the nonclonability of quantum information-is a fundamental principle of quantum mechanics, an impossibility theorem for the broadcasting of general density matrices has not yet been formulated. In this Letter, we present a general proof for the no-broadcasting theorem, which applies to arbitrary density matrices. The proof relies on entropic considerations, and as such can also be directly linked to its classical counterpart, which applies to probabilistic distributions of statistical ensembles.

The dynamics of spatial behavior: how can robust smoothing techniques help?

A variety of setups and paradigms are used in the neurosciences for automatically tracking the location of an animal in an experiment and for extracting features of interest out of it. Many of these features, however, are critically sensitive to the unavoidable noise and artifacts of tracking. Here, we examine the relevant properties of several smoothing methods and suggest a combination of methods for retrieving locations and velocities and recognizing arrests from time series of coordinates of an animal's center of gravity. We accomplish these by using robust nonparametric methods, such as Running Median (RM) and locally weighted regression methods. The smoothed data may, subsequently, be segmented to obtain discrete behavioral units with proven ethological relevance. New parameters such as the length, duration, maximal speed, and acceleration of these units provide a wealth of measures for, e.g., mouse behavioral phenotyping, studies on spatial orientation in vertebrates and invertebrates, and studies on rodent hippocampal function. This methodology may have implications for many tests of spatial behavior.